package srcStableMatching;

import java.io.BufferedWriter;
import java.io.FileWriter;
import java.util.ArrayList;
import java.util.Collections;
import java.util.List;
import java.util.Random;

import lib.logging.ANSIConsoleLogger;
import lib.logging.ILogger;

public class StableMatching
{
    private static Random RandomGenerator = new Random();

    private static double ComputeGoodnessAvg(
            List<Double> normalizedMenGoodnessList)
    {
        double sum = 0;
        for (int i = 2; i < normalizedMenGoodnessList.size() - 2; ++i)
        {
            sum += normalizedMenGoodnessList.get(i);
        }

        return sum / (normalizedMenGoodnessList.size() - 4);
    }

    /**
     * Uses "inside-out" shuffle algorithm to generate a random permutation of numbers 0 to size - 1
     * http://en.wikipedia.org/wiki/Knuth_shuffle#The_.22inside-out.22_algorithm
     *
     * @param size
     * @return random permutation of numbers 0 to size - 1
     */
    private static int[] GetRandomPermutation(int size)
    {
        int[] arr = new int[size];
        arr[0] = 0;

        for (int i = 1; i < size; ++i)
        {
            // get random number in range 0 to i (both inclusive)
            int randomIndex = RandomGenerator.nextInt(i + 1);
            arr[i] = arr[randomIndex];
            arr[randomIndex] = i;
        }

        return arr;
    }

    private static int[][] GetRandomPreferenceLists(int size)
    {
        int[][] prefs = new int[size][size];

        for (int i = 0; i < size; ++i)
        {
            prefs[i] = GetRandomPermutation(size);
        }

        return prefs;
    }

    /**
     * @param args
     * @throws Exception
     */
    public static void main(String[] args) throws Exception
    {
        ILogger consoleLogger = new ANSIConsoleLogger();

        try
        {
            BufferedWriter bufWriter = new BufferedWriter(
                    new FileWriter("StableMatchingOutput.csv"));

            for (int size = 1; size < 10000; ++size)
            {
                List<Double> normalizedMenGoodnessList = new ArrayList<Double>();
                List<Double> normalizedWomenGoodnessList = new ArrayList<Double>();

                for (int i = 0; i < 10; ++i)
                {
                    int[][] menPrefs = GetRandomPreferenceLists(size);
                    int[][] womenPrefs = GetRandomPreferenceLists(size);

                    StableMatching stableMatching = new StableMatching(size, menPrefs, womenPrefs, consoleLogger);
                    stableMatching.GenerateStableMatching();

                    // stableMatching.PrintMatching();

                    int menGoodness = stableMatching.CalculateMenGoodness();
                    int womenGoodness = stableMatching.CalculateWomenGoodness();

                    double normalizedMenGoodness = (double) (menGoodness) / size;
                    double normalizedWomenGoodness = (double) womenGoodness / size;

                    normalizedMenGoodnessList.add(normalizedMenGoodness);
                    normalizedWomenGoodnessList.add(normalizedWomenGoodness);

                    /*
                    consoleLogger.LogInfo(
                            "normalizedMenGoodness: %f, normalizedWomenGoodness: %f",
                            normalizedMenGoodness,
                            normalizedWomenGoodness);
                    */
                }

                Collections.sort(normalizedMenGoodnessList);
                Collections.sort(normalizedWomenGoodnessList);

                double avgMenGoodness = ComputeGoodnessAvg(normalizedMenGoodnessList);
                double avgWomenGoodness = ComputeGoodnessAvg(normalizedWomenGoodnessList);


                consoleLogger.LogInfo(
                        "size: %d, avgMenGoodness: %f, avgWomenGoodness: %f",
                        size,
                        avgMenGoodness,
                        avgWomenGoodness);

                bufWriter.write(String.format("%d, %f, %f", size, avgMenGoodness, avgWomenGoodness));
                bufWriter.newLine();
                bufWriter.flush();
            }

            bufWriter.close();
        }
        catch (Exception ex)
        {
            consoleLogger.LogException(ex);
            throw ex;
        }
    }

    /**
     * List of men currently free
     */
    private List<Integer> freeMen;

    /**
     * For each man, stores index of next women he is supposed to propose in his preference list
     */
    private int[] nextToProposeForMen;

    /**
     * For each woman, stores id of man with whom she is currently engaged.
     * A value of -1 means she is currently free.
     */
    private int[] currentEngagementOfWomen;

    /**
     * For each woman, stores the rank of each man on her preference list
     * Helps in looking up the rank of a man in a woman's preference list in O(1) time, for comparison between two men.
     */
    private int[][] menRankingForWomen;

    /**
     * For each man, stores the rank of each woman on his preference list
     * Helps in looking up the rank of a man in a woman's preference list in O(1) time
     */
    private int[][] womenRankingForMen;

    /**
     * Number of men/women.
     */
    int size;

    /**
     * Preference lists for men.
     * Values for each man, are stored in decreasing preferences.
     */
    int[][] menPreferences;

    /**
     * Preference lists of women.
     * Values for each woman, are stored in decreasing preferences.
     */
    int[][] womenPreferences;

    /**
     * Logger for printing messages to console
     */
    private ILogger logger;

    /**
     * Constructor
     *
     * @param size
     * @param menPreferences
     * @param womenPreferences
     */
    public StableMatching(int size, int[][] menPreferences, int[][] womenPreferences, ILogger logger)
    {
        this.size = size;
        this.menPreferences = menPreferences;
        this.womenPreferences = womenPreferences;
        this.logger = logger;

        InitializeFreeMen();
        InitializeNextWomanForMen();
        InitializeCurrentEngagementOfWomen();
        InitializeMenRankingForWomen();
        InitializeWomenRankingForMen();
    }

    private int CalculateMenGoodness()
    {
        int goodness = 0;

        for (int i = 0; i < this.size; ++i)
        {
            int man = this.currentEngagementOfWomen[i];
            goodness += this.womenRankingForMen[man][i] + 1;
        }

        return goodness;
    }

    private int CalculateWomenGoodness()
    {
        int goodness = 0;

        for (int i = 0; i < this.size; ++i)
        {
            int man = this.currentEngagementOfWomen[i];
            goodness += this.menRankingForWomen[i][man] + 1;
        }

        return goodness;
    }

    private void GenerateStableMatching()
    {
        while(!this.freeMen.isEmpty())
        {
            int man = this.freeMen.get(0);
            this.freeMen.remove(0);

            int womanToPropose = this.menPreferences[man][this.nextToProposeForMen[man]];
            ++this.nextToProposeForMen[man];

            Propose(man, womanToPropose);
        }
    }

    /**
     * Initializes current engagement for all women to -1 (i.e free)
     */
    private void InitializeCurrentEngagementOfWomen()
    {
        this.currentEngagementOfWomen = new int[this.size];

        for (int i = 0; i < this.size; ++i)
        {
            this.currentEngagementOfWomen[i] = -1;
        }
    }

    /**
     * Adds all men to the list of free men.
     */
    private void InitializeFreeMen()
    {
        this.freeMen = new ArrayList<Integer>();

        for (int i = 0; i < this.size; ++i)
        {
            this.freeMen.add(i);
        }
    }

    /**
     * Initializes the ranking matrix based on women's preference list
     */
    private void InitializeMenRankingForWomen()
    {
        this.menRankingForWomen = new int[this.size][this.size];

        for (int i = 0; i < this.size; ++i)
        {
            for (int j = 0; j < this.size; ++j)
            {
                this.menRankingForWomen[i][this.womenPreferences[i][j]] = j;
            }
        }
    }

    /**
     * Initializes next woman for each man to 0 i.e first woman
     */
    private void InitializeNextWomanForMen()
    {
        this.nextToProposeForMen = new int[this.size];

        for (int i = 0; i < this.size; ++i)
        {
            this.nextToProposeForMen[i] = 0;
        }
    }

    /**
     * Initializes the ranking matrix based on men's preference lists
     */
    private void InitializeWomenRankingForMen()
    {
        this.womenRankingForMen = new int[this.size][this.size];

        for (int i = 0; i < this.size; ++i)
        {
            for (int j = 0; j < this.size; ++j)
            {
                this.womenRankingForMen[i][this.menPreferences[i][j]] = j;
            }
        }

    }

    private void PrintMatching()
    {
        for (int i = 0; i < this.size; ++i)
        {
            this.logger.LogInfo(
                    "W%d, M%d",
                    i,
                    this.currentEngagementOfWomen[i]);
        }
    }

    private void Propose(int man, int womanToPropose)
    {
        int existingMan = this.currentEngagementOfWomen[womanToPropose];

        if (existingMan == -1)
        {
            this.currentEngagementOfWomen[womanToPropose] = man;
        }
        else
        {
            int manRanking = this.menRankingForWomen[womanToPropose][man];
            int existingManRanking = this.menRankingForWomen[womanToPropose][existingMan];

            if (manRanking < existingManRanking)
            {
                this.currentEngagementOfWomen[womanToPropose] = man;
                this.freeMen.add(existingMan);
            }
            else
            {
                this.freeMen.add(man);
            }
        }
    }
}
